package leetcode.code2074;

import leetcode.helper.MaxDebug;
import leetcode.helper.tree.ListNode;

public class Solution extends Solution2074 {

	@Override
	public ListNode reverseEvenLengthGroups(ListNode head) {
		ListNode p = head.next;
		if (p == null) {// 只有一个节点，直接返回
			return head;
		}
		// head不动了，跨过head直接处理head后第一个节点，起始就是偶数，长度2
//		boolean even = true; 搞错了，开始以为是偶数组颠倒，实际是即将处理的个数决定奇偶性
		int next = 2;
		int move = 2;// 第一个目标移动距离是偶数
		ListNode tail = head;
		while (p != null) {
			// 处理后续之前，得决定是否颠倒，这个位置可以和奇数个操作合并，如果走完是奇数结束，如果
			int count = 0;
			ListNode tryCount = p;
			int tryMove = move;
			while (tryMove > 0 && tryCount != null) {
				tryCount = tryCount.next;
				count++;
				tryMove--;
			}
			if ((count & 1) == 0) {// 偶数 even
				ListNode p1 = p;// 反向尾巴
				ListNode p0 = p;// 反向头
				ListNode p2 = p1.next;
				move -= 1;
				while (move > 0 && p2 != null) {
					p1 = p2;
					p2 = p1.next;
					p1.next = p0;
					p0 = p1;
					move--;
				}
				p.next = p2;// 反向尾.next = 下段头。尾接头
				tail.next = p0;// 前段尾.next = 反向头。尾接头
				tail = p;// 更新尾，p变成前段尾
				p = p2;// 更新头，p2变成下段头
//				even = !even;// 颠倒奇偶
				next += 1;// 下一段长度
				move = next;// 下一段需要移动的长度
			} else {// 奇数往往下走
				while (move > 0 && p != null) {
					tail.next = p;
					tail = tail.next;
					p = p.next;
					move--;
				}
//				even = !even;// 颠倒奇偶
				next += 1;// 下一段长度
				move = next;// 下一段需要移动的长度
			}
		}
		return head;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		MaxDebug.debug14(so);

	}

}
